class Solution {
public:
    int ret = 0;
    bool visted[16];
    void dfs(int cur, int n)
    {
        if (cur == n + 1)
        {
            ret++;
            return;
        }

        for (int i = 1; i <= n; i++)
        {
            if (visted[i] == false && (cur % i == 0 || i % cur == 0))
            {
                visted[i] = true;
                dfs(cur + 1, n);
                visted[i] = false;
            }
        }
    }
    int countArrangement(int n)
    {
        dfs(1, n);
        return ret;
    }
};